HW#3 --- last modified February 06 2019 04:19:23..

Solution set.

Due date: Apr 6

Files to be submitted:
  Hw3.zip

Purpose:

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO2 -- By code or by hand translate sentences in logic to conjunctive normal form (CNF).

LO3 -- By code or by hand find proofs by using resolution.

LO7 -- Students should be able to explain the advantages and disadvantages of forward checking in constraint satisfaction.

Specification:

This homework consists of a written component and a coding component. Files for both components should be submitted in your Hw3.zip file along with a readme.txt with any additional instructions, a list of your team mates and their IDs. For the written part, please do the following problems and submit them in a file Hw3.pdf within the Hw3.zip file.

1. By hand, carefully using the definition of CSP, formulate the map coloring problem for the District Map of San Jose as a constraint satisfaction problem. You can assume we are trying to color using four colors: blue, chartreuse, green, and red.
2. If we use the degree heuristic to choose the first variable in backtracking search and if we break ties by picking the smaller numbered district, which variable would be considered first by our backtracking algorithm? Show why. Assume District 9 is connected to District 7.
3. Suppose we color District 7 blue. (a) Show all of the domains for each district after doing an arc consistency check. (b) For District 2, show carefully the steps in running REVISE(csp, District 2, District 7), you don't need to go into this much detail for (a).
4. Using the MINIMUM REMAINING VALUE heuristic, choose the node to consider next. Break ties by choosing the district of smaller number. Consider colors from the domain using the LEAST-CONSTRAINING-VARIABLE heuristic breaking ties by picking the color of earlier alphabetic order. Assign the node this color. Draw the graph listing the current domains by each node. Do arc consistency, and draw the graph again.
5. Continue doing the backtracking search algorithm until you have colored the whole graph. Draw this graph with the colors indicated. (You don't need to show all the steps to get this.) If we had not done arc consistency checks (forward checking), how would the backtracking algorithm have been slower?
6. Come up with a logical formula which expresses `W_(3,3)`, there is a Wumpus in square (3,3), in terms of the variables (more than one) `S_(x,y)` expressing there is a stench in square (x,y). Convert this formula to CNF by hand by first doing biconditional elimination, then implication elimination, then using distributivity. Check your work by downloading the software from Russell and Norvig, launching the Python interpreter, typing from logic import * then doing to_cnf("your original formula"). Obviously, replace "your original formula" with the formula you had before converting to CNF. Have the transcript of your interaction with Python as part of your solution.

For the coding part of the assignment I want you to write an agent for a variant of the Wumpus World problem I call Oozplorer. Like the Wumpus World we have an explorer that starts on square (1,1). The world is played on an `n times n` board of square. One square randomly chosen other than (1,1) has gold. Each square other than (1,1) and the one containing the gold has a pit with probability 0.2. The only sensory data is a breeze which is detected in a square next to a salt pit. This game doesn't have a wumpus or arrows. We imagine the explorer being some kind of gelatinous ooze, an Oozplorer, rather than a person that can only occupy one square at a time. In one turn the Oozplorer can spread itself into an square adjacent to any of the squares it currently occupies. If it encounters a salt pit the Oozplorer shrivels, dies, and loses. If the Oozplorer enters a square with gold, it immediately wins.

Your program will be run from the command line with the command:

python oozplorer.py some_number

For example,

python oozplorer.py 4

Your program should have at least two classes: Agent and Board. It should have a driver program which first creates a new Board passing in some_number. Then it calls the constructor for Agent with some_number and this board object. Finally, the program calls, the Agent's start(self) method. The constructor of Board when called with the value from the command line argument should build a board with properties described above that will be used for the game. A square in this board, should maintain whether it has a breeze, is occupied by the oozplorer, has a pit, or has gold. In addition to the constructor, the Board class should have a method move(self, pair). Here pair is a tuple with an x,y coordinates. This method returns a (sensor, state). The method throws an exception if (x,y) is not either a square currently occupied by the oozplorer or adjacent to an occupied square. Here sensor returns True if there is a breeze in that square and False otherwise. Here state is -1 if the oozplorer loses moving into that square, 1 if it wins, and 0 otherwise. If the square didn't have the oozplorer, and it was a legal move, then as a side effect of the move call, the square is updated to now be occupied by the oozplorer, and the board is draw to stdout so a human observer can see what is going on.

The Agent class should also have a constructor which makes use of some_number to build an initial knowledge base (consisting of rules like we did in class). Please leverage the code downloaded from the book's website to do this. In your Hw3.zip, you may include the files logic.py, utils.py, and agents.py from the books code. The start(self) method of Agent has a loop which exits only if the oozeplayer wins or loses. In this loop, the Agent picks a node from its frontier, and tries to use logic.dpll_satisfiable to prove that the square does not have a pit. Agent is only allowed to use Board's move method to figure out things about the world that Board maintain. If it proves this, then it oozes into that square by calling its Board's move method. This should also draw the board. If it can't prove this, it should try the next node in its frontier. If none of the nodes in its frontier can be proven safe, it should move to the first square it tried from its frontier.

Here is an example output that your program could produce (. - empty square, P - pit, G - gold, @ - oozplorer occupied):

python oozplorer.py 4
Move 0
P...
..G.
...P
.P
@@P.

Move 3
P...
..G.
@G.
@@@P
@@P.

Move 6
P...
@@G.
@@@P
@@P.

Move 7
P...
@@@.
@@@P
@@P.

Gold Found!
Oozplorer wins!

Point Breakdown